package com.leetcode.dp;

import java.util.*;

/**
 * 单词拆分
 * 给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
 * 说明：
 * 拆分时可以重复使用字典中的单词。
 * 你可以假设字典中没有重复的单词。
 * 示例 1：
 * 输入: s = "leetcode", wordDict = ["leet", "code"]
 * 输出: true
 * 解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
 * 示例 2：
 * 输入: s = "applepenapple", wordDict = ["apple", "pen"]
 * 输出: true
 * 解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
 * 注意你可以重复使用字典中的单词。
 * 示例 3：
 * 输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
 * 输出: false
 * 作者：力扣 (LeetCode)
 * 链接：https://leetcode-cn.com/leetbook/read/top-interview-questions/xa503c/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 * @author ymy
 * @date 2021年09月02日 17:49
 */
class Code139 {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("a");
        list.add("aa");
        list.add("aaa");
        list.add("aaaa");
        list.add("aaaaa");
        list.add("aaaaaa");
        list.add("aaaaaaa");
        list.add("aaaaaaaa");
        list.add("aaaaaaaaa");
        list.add("aaaaaaaaaa");
        String s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
        Code139 word = new Code139();
        boolean res = word.test(s,list);
        System.out.println("flag="+res);
    }

    /**
     * 解法1：动态规划
     * 思路和算法
     * 我们定义 dp[i] 表示字符串 s 前 i 个字符组成的字符串 s[0..i−1] 是否能被空格拆分成若干个字典中出现的单词。
     * 从前往后计算考虑转移方程，每次转移的时候我们需要枚举包含位置 i−1 的最后一个单词，看它是否出现在字典中以及除去这部分的字符串是否合法即可
     * 公式化来说，我们需要枚举 s[0..i−1] 中的分割点 j ，看 s[0..j−1] 组成的字符串 s1 (默认 j = 0 时 s1为空串）和 s[j..i-1]s[j..i−1] 组成的字符串 s2是否都合法，
     * 如果两个字符串均合法，那么按照定义 s1 和 s2 拼接成的字符串也同样合法。
     * 由于计算到 dp[i] 时我们已经计算出了 dp[0..i−1] 的值，因此字符串 s1 是否合法可以直接由 dp[j] 得知，剩下的我们只需要看 s2 是否合法即可，
     * 因此我们可以得出如下转移方程：dp[i]=dp[j] && check(s[j..i−1])
     * 其中 check(s[j..i−1]) 表示子串 s[j..i−1] 是否出现在字典中。
     * 对于检查一个字符串是否出现在给定的字符串列表里一般可以考虑哈希表来快速判断，同时也可以做一些简单的剪枝，枚举分割点的时候倒着枚举，
     * 如果分割点 j 到 i 的长度已经大于字典列表里最长的单词的长度，那么就结束枚举，但是需要注意的是下面的代码给出的是不带剪枝的写法。
     * 对于边界条件，我们定义 dp[0]=true 表示空串且合法。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/word-break/solution/dan-ci-chai-fen-by-leetcode-solution/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordDictSet = new HashSet(wordDict);
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordDictSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
    /**
     * 解法2：回溯
     * 使用回溯算法，对于s中的每个位置，探索的范围就是wordDict中的每个单词
     * 做两点优化：
     * 1、对wordDict按照字符串长度从小到大排序，探索时，如当前位置+wordDict中单词长度大于s的长度时，没必要继续探索了；
     * 2、memory[i]记录当前位置已经尝试过的wordDict中且尝试失败的元素；
     *
     * 作者：caixiaopang
     * 链接：https://leetcode-cn.com/problems/word-break/solution/jian-dan-de-hui-su-suan-fa-chao-guo-80de-mark/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    public boolean wordBreak1(String s, List<String> wordDict) {
        Set<Integer>[] memory = new Set[s.length()];
        for (int i = 0; i < memory.length; i++) {
            memory[i] = new HashSet<>();
        }
        wordDict.sort(Comparator.comparingInt(value -> value.length()));
        return back(0, s, wordDict, memory);
    }

    private boolean back(int idx, String s, List<String> wordDict, Set<Integer>[] memory) {
        if (idx >= s.length()) {
            return true;
        }
        for (int i = 0; i < wordDict.size(); i++) {
            if (idx + wordDict.get(i).length() > s.length()) {
                return false;
            }
            if (memory[idx].contains(i)) {
                continue;
            }
            if (s.substring(idx, idx + wordDict.get(i).length()).equals(wordDict.get(i))) {
                if (back(idx + wordDict.get(i).length(), s, wordDict, memory)) {
                    return true;
                } else {
                    memory[idx].add(i);
                }
            }
        }
        return false;
    }


    public boolean test(String s, List<String> wordDict){
        Set<String> set = new HashSet<>(wordDict);
        boolean dp[] = new boolean[s.length()+1];
        dp[0] = true;
        for(int i=1;i<=s.length();i++){
            for(int j = 0;j<i;j++){
                if(dp[j] && set.contains(s.substring(j,i))){
                    dp[i] = true;
                }
            }
        }
        return dp[dp.length-1];
    }
}
